import java.util.Arrays;
import java.util.Scanner;

class SortProgram {
    public static void main(String[] args) {
        int[] data = {5, 3, 8, 4, 2, 7, 6, 1};
        System.out.println("初始数据: " + Arrays.toString(data));

        int choice = 0; // 0 for Insertion Sort, 1 for Quick Sort, 2 for Selection Sort
        do {
            System.out.println("选择: \n0. 直接插入排序\n1. 快速排序\n2. 选择排序\n3. 退出");
            choice = Integer.parseInt(input());
        } while (choice < 0 || choice > 3);

        switch (choice) {
            case 0:
                insertionSort(data);
                break;
            case 1:
                quickSort(data, 0, data.length - 1);
                break;
            case 2:
                selectionSort(data);
                break;
        }

        System.out.println("选择排序: " + Arrays.toString(data));
    }

    static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

    static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }

    static String input() {
        java.util.Scanner scanner = new java.util.Scanner(System.in);
        return scanner.nextLine();
    }
}



public class Main {
    public static void main(String[] args) {
        int[] data = {5, 3, 8, 4, 2, 7, 6, 1};
        System.out.println("初始数据: " + Arrays.toString(data));

        int choice;
        do {
            System.out.println("选择: \n0. 直接插入排序\n1. 快速排序\n2. 选择排序\n3. 退出");
            Scanner scanner = new Scanner(System.in);
            choice = scanner.nextInt();
            scanner.nextLine(); // Consume newline left-over

            switch (choice) {
                case 0:
                    insertionSort(data);
                    break;
                case 1:
                    quickSort(data, 0, data.length - 1);
                    break;
                case 2:
                    selectionSort(data);
                    break;
                case 3:
                    System.out.println("退出");
                    return;
                default:
                    System.out.println("无该选项，请重新输入");
                    break;
            }

            System.out.println("选择排序： " + Arrays.toString(data));
        } while (choice != 3);
    }

    static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

    static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }
}